package sort;

/**
 * Created by huangyx on 2017/8/4 0004.
 */
public class MaxPQ<Key extends Comparable<Key>> {

    private Key[] pq;   //基于堆的完全二叉树
    private int N = 0;  //存储于pq[1...N]中，pq[0]没有使用

    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }

    public Key delMax() {
        Key max = pq[1];
        swap(1, N--);
        pq[N + 1] = null;
        sink(1);
        return max;
    }

    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int k = N / 2; k >= 1; k--) {
//            sink(a, k, N);
            while (N > 1) {
//                swap(a, 1, N--);
//                sink(a, 1, N);
            }
        }
    }


    /*辅助方法*/

    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    private void swap(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }

    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            swap(k / 2, k);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(j, j + 1))
                j++;
            if (!less(k, j))
                break;
            swap(k, j);
            k = j;
        }
    }

}
